import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/21 11:56
 * @description BFS
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] richer = {{1,0},{2,1},{3,1},{3,7},{4,3},{5,3},{6,3}};
        int[] quiet = {3,2,5,4,6,1,7,0};
        solution.loudAndRich(richer, quiet);
    }
    List<Integer>[] edges;
    int[] in;
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int n = quiet.length;
        edges = new List[n];
        for (int i = 0; i < n; i++) {
            edges[i] = new ArrayList<>();
        }
        in = new int[n];
        for (int[] r: richer) {
            // 反向 x -> y 说明 后边的钱永远更少
            edges[r[0]].add(r[1]);
            ++in[r[1]];
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            ans[i] = i;
        }
        Queue<Integer> q = new ArrayDeque<Integer>();
        for (int i = 0; i < n; ++i) {
            if (in[i] == 0) {
                q.offer(i);
            }
        }
        while (!q.isEmpty()) {
            int x = q.poll();
            for (int y : edges[x]) {
                if (quiet[ans[x]] < quiet[ans[y]]) {
                    // 更新 x 的邻居的答案
                    ans[y] = ans[x];
                }
                if (--in[y] == 0) {
                    q.offer(y);
                }
            }
        }
        return ans;
    }
}
